#pragma once
#include <iostream>
#include <unordered_map>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <climits>

// 带边值的有向图，出边表储存
template <class VexValue, class EdgeValue>
class BaseGraph {
protected:
    std::unordered_map<int, VexValue> _vexList;
    std::unordered_map<int, std::unordered_map<int, EdgeValue>> _outEdgeList;

    void DFSpartly(int _start, void (*Visit)(VexValue&), std::vector<bool>& IsVisited);
public:
    BaseGraph() {};
    virtual ~BaseGraph() {};

    bool IsEmpty() const { return _vexList.empty(); }
    void Clear() { _vexList.clear(); _outEdgeList.clear(); }

    void DFStraversal(void (*Visit)(VexValue&));
    void BFStraversal(void (*Visit)(VexValue&));
};

template <class VexValue, class EdgeValue>
void BaseGraph<VexValue, EdgeValue>::DFSpartly(int _start, void (*Visit)(VexValue&), std::vector<bool>& IsVisited) {
    (*Visit)(_vexList.at(_start));
    IsVisited[_start] = true;
    for (auto i = _outEdgeList.at(_start).begin(); i != _outEdgeList.at(_start).end(); ++i) {
        if (IsVisited[i->first])
            continue;
        DFSpartly(i->first, Visit, IsVisited);
    }
}

template <class VexValue, class EdgeValue>
void BaseGraph<VexValue, EdgeValue>::DFStraversal(void (*Visit)(VexValue&)) {
    std::vector<bool> IsVisited(_vexList.size(), false);
    for (int i = 0; i < _vexList.size(); ++i) {
        if (IsVisited[i])
            continue;
        DFSpartly(i, Visit, IsVisited);
    }
}

template <class VexValue, class EdgeValue>
void BaseGraph<VexValue, EdgeValue>::BFStraversal(void (*Visit)(VexValue&)) {
    std::deque<int> quene;
    std::vector<bool> IsVisited(_vexList.size(), false);

    for (int i = 0; i < _vexList.size(); i++) {
        if (IsVisited[i])
            continue;
        quene.push_back(i);
        while (!quene.empty())
        {
            int top = quene.front();
            quene.pop_front();
            if (IsVisited[top])
                continue;
            (*Visit)(_vexList[top]);
            IsVisited[top] = true;

            for (auto j = _outEdgeList.at(top).begin(); j != _outEdgeList.at(top).end(); ++j) {
                if (IsVisited[j->first])
                    continue;
                quene.push_back(j->first);
            }
        }
    }
}

template <class EdgeValue>
struct EdgeNode
{
    int from, to;
    bool isNaN;
    EdgeValue value;
    EdgeNode(const int _from, const int _to, const EdgeValue& _value) {
        from = _from; to = _to; isNaN = false; value = _value;
    }
    EdgeNode(const int _from, const int _to) {
        from = _from; to = _to; isNaN = true;
    }
    bool operator<(const EdgeNode& other) const {
        if (isNaN)
            return false;
        if (other.isNaN)
            return true;
        return value < other.value;
    }
};

#define VexType char
#define EdgeType int
#define EdgeNaN INT_MAX

// 最短路径节点，Dijkstra算法
template <class VexValue, class EdgeValue>
struct ShoPathNode
{
    VexValue vertex;
    EdgeValue length;
    int preVex;
    ShoPathNode(const VexValue& _ver, const int _pre, const EdgeValue& _length) : 
        vertex(_ver), length(_length), preVex(_pre) {}
    ShoPathNode(const VexValue& _ver, const int _pre) : 
        vertex(_ver), length(EdgeNaN), preVex(_pre) {};
    bool operator<(const ShoPathNode& other) const {return length < other.length;}
};

// 无向带权图（网络）
class UndiGraph : public BaseGraph<VexType, EdgeType>
{
public:
    UndiGraph() {};
    ~UndiGraph() {};
    friend std::istream& operator>>(std::istream& in, UndiGraph& _graph);
    void MSTprime(std::vector<EdgeNode<EdgeType>>& mst) const;
    void MSTKruskal(std::vector<EdgeNode<EdgeType>>& mst) const;

    void ShortedPathDijkstra(int start, std::vector<ShoPathNode<VexType, EdgeType>>& shoPath);
};

std::istream& operator>>(std::istream& in, UndiGraph& _graph) {
    int verSize;
    in >> verSize;

    std::unordered_map<int, EdgeType> temp;
    for (int i = 0; i < verSize; i++) {
        _graph._vexList.emplace(i, 'A' + i);
        _graph._outEdgeList.emplace(i, temp);
    }
    for (int i = 0; i < verSize - 1; i++) {
        int edgeSize;
        VexType from;

        in >> from;
        in >> edgeSize;
        for (int j = 0; j < edgeSize; j++) {
            EdgeType value;
            VexType to;
            in >> to >> value;
            _graph._outEdgeList.at(from - 'A').emplace(to - 'A', value);
            // 无向图
            _graph._outEdgeList.at(to - 'A').emplace(from - 'A', value);
        }

    }
    return in;
}

void UndiGraph::MSTprime(std::vector<EdgeNode<int>>& mst) const {
    int min_pos = 0;

    mst.clear();
    for (int to = 1; to < _vexList.size(); to++) {
        auto val = _outEdgeList.at(0).find(to);
        if (val == _outEdgeList.at(0).end())
            mst.emplace_back(0, to);
        else
        {
            mst.emplace_back(0, to, val->second);
            if (mst[to - 1] < mst[min_pos])
                min_pos = to - 1;
        }
    }
    EdgeNode<EdgeType> swapTemp = mst[0];
    mst[0] = mst[min_pos];
    mst[min_pos] = swapTemp;

    int to_new = mst[0].to;

    for (int not_count = 1; not_count < mst.size(); not_count++)
    {
        min_pos = not_count;
        for (int j = not_count; j < mst.size(); j++)
        {
            auto val = _outEdgeList.at(to_new).find(mst[j].to);
            if (val != _outEdgeList.at(to_new).end() && (mst[j].isNaN || val->second < mst[j].value))
            {
                mst[j].from = to_new;
                mst[j].isNaN = false;
                mst[j].value = val->second;
            }
            if (mst[j] < mst[min_pos])
                min_pos = j;
        }
        EdgeNode<EdgeType> swapTemp = mst[not_count];
        mst[not_count] = mst[min_pos];
        mst[min_pos] = swapTemp;
        // 处理边
        // ...
        to_new = mst[not_count].to;
    }
}

void UndiGraph::MSTKruskal(std::vector<EdgeNode<EdgeType>>& mst) const {
    mst.clear();
    std::multimap<EdgeType, std::pair<int, int>> minHeap;
    std::pair<int, int> temp;
    for (auto i = _outEdgeList.begin(); i != _outEdgeList.end(); ++i) {
        temp.first = i->first;
        for (auto j = i->second.begin(); j != i->second.end(); ++j) {
            temp.second = j->first;
            minHeap.emplace(j->second, temp);
        }
    }
    std::vector<int> uniFind;
    int id = 0;
    for (int i = 0; i < _vexList.size(); i++) {
        uniFind.push_back(i);
    }

    for (auto i = minHeap.begin(); mst.size() < _vexList.size() - 1 && i != minHeap.end(); ++i) {
        int parent = uniFind[i->second.first];
        while (uniFind[parent] != parent) {
            parent = uniFind[parent];
        }
        uniFind[i->second.first] = parent;
        parent = uniFind[i->second.second];
        while (uniFind[parent] != parent) {
            parent = uniFind[parent];
        }
        uniFind[i->second.second] = parent;

        if (uniFind[i->second.first] == uniFind[i->second.second])
            continue;
        parent = uniFind[i->second.first];
        uniFind[parent] = uniFind[i->second.second];
        // 处理边
        // ...
        mst.emplace_back(i->second.first, i->second.second, i->first);
    }
}

void UndiGraph::ShortedPathDijkstra(int start, std::vector<ShoPathNode<VexType, EdgeType>>& shoPath) {
    shoPath.clear();
    // to, value
    std::list<std::pair<int, EdgeType>> noInced;
    std::list<std::pair<int, EdgeType>>::iterator min_pos;
    auto startOut = _outEdgeList.at(start);
    for (int i = 0; i < _vexList.size(); i++) {
        if (i == start) {
            shoPath.emplace_back(_vexList.at(i), start, 0);
            continue;
        }
        auto temp = startOut.find(i);
        if (temp == startOut.end()) {
            shoPath.emplace_back(_vexList.at(i), start);
            noInced.emplace_back(i, EdgeNaN);
        }
        else {
            shoPath.emplace_back(_vexList.at(i), start, temp->second);
            noInced.emplace_back(i, temp->second);
        }
    }
    min_pos = noInced.begin();
    for (auto i = noInced.begin(); i != noInced.end(); ++i) {
        if (i->second < min_pos->second)
            min_pos = i;
    }
    while (!noInced.empty())
    {
        auto minOutList = _outEdgeList.at(min_pos->first);
        std::pair<int, EdgeType> minElem = *min_pos;
        noInced.erase(min_pos);
        min_pos = noInced.begin();
        for (auto i = noInced.begin(); i != noInced.end(); ++i) {
            auto res = minOutList.find(i->first);
            if (res == minOutList.end()) {
                if (i->second < min_pos->second)
                    min_pos = i;
                continue;
            }
            if (minElem.second +  res->second < i->second) {
                i->second = minElem.second +  res->second;
                shoPath.at(i->first).length = minElem.second +  res->second;
                shoPath.at(i->first).preVex = minElem.first;
            }
            if (i->second < min_pos->second)
                min_pos = i;
        }
    }
}

class DiGraph : public BaseGraph<VexType, EdgeType>
{
public:
    DiGraph() {};
    ~DiGraph() {};
    friend std::istream& operator>>(std::istream& in, DiGraph& _graph);
    void ShortedPathDijkstra(int start, std::vector<ShoPathNode<VexType, EdgeType>>& shoPath);
    void ShortedPathFloyd(std::vector<std::vector<EdgeType>>& valueMat, std::vector<std::vector<int>>& nextMat);
    void TopoOnAOV(std::vector<VexType>& topo);
};

std::istream& operator>>(std::istream& in, DiGraph& _graph) {
    int verSize;
    in >> verSize;

    std::unordered_map<int, EdgeType> temp;
    for (int i = 0; i < verSize; i++) {
        _graph._vexList.emplace(i, 'A' + i);
        _graph._outEdgeList.emplace(i, temp);
    }
    for (int i = 0; i < verSize; i++) {
        int edgeSize;
        VexType from;

        in >> from;
        in >> edgeSize;
        for (int j = 0; j < edgeSize; j++) {
            EdgeType value;
            VexType to;
            in >> to >> value;
            _graph._outEdgeList.at(from - 'A').emplace(to - 'A', value);
        }
    }
    return in;
}

void DiGraph::ShortedPathDijkstra(int start, std::vector<ShoPathNode<VexType, EdgeType>>& shoPath) {
    shoPath.clear();
    // to, value
    std::list<std::pair<int, EdgeType>> noInced;
    std::list<std::pair<int, EdgeType>>::iterator min_pos;
    auto startOut = _outEdgeList.at(start);
    for (int i = 0; i < _vexList.size(); i++) {
        if (i == start) {
            shoPath.emplace_back(_vexList.at(i), start, 0);
            continue;
        }
        auto temp = startOut.find(i);
        if (temp == startOut.end()) {
            shoPath.emplace_back(_vexList.at(i), start);
            noInced.emplace_back(i, EdgeNaN);
        }
        else {
            shoPath.emplace_back(_vexList.at(i), start, temp->second);
            noInced.emplace_back(i, temp->second);
        }
    }
    min_pos = noInced.begin();
    for (auto i = noInced.begin(); i != noInced.end(); ++i) {
        if (i->second < min_pos->second)
            min_pos = i;
    }
    while (!noInced.empty())
    {
        auto minOutList = _outEdgeList.at(min_pos->first);
        std::pair<int, EdgeType> minElem = *min_pos;
        noInced.erase(min_pos);
        min_pos = noInced.begin();
        for (auto i = noInced.begin(); i != noInced.end(); ++i) {
            auto res = minOutList.find(i->first);
            if (res == minOutList.end()) {
                if (i->second < min_pos->second)
                    min_pos = i;
                continue;
            }
            if (minElem.second +  res->second < i->second) {
                i->second = minElem.second +  res->second;
                shoPath.at(i->first).length = minElem.second +  res->second;
                shoPath.at(i->first).preVex = minElem.first;
            }
            if (i->second < min_pos->second)
                min_pos = i;
        }
    }
}

void DiGraph::ShortedPathFloyd(std::vector<std::vector<EdgeType>>& valueMat, std::vector<std::vector<int>>& nextMat) {
    for (int i = 0; i < valueMat.size(); i++)
        valueMat[i].clear();
    valueMat.clear();
    for (int i = 0; i < nextMat.size(); i++)
        nextMat[i].clear();
    nextMat.clear();
    for (int i = 0; i < _vexList.size(); i++) {
        auto outList = _outEdgeList.at(i);
        valueMat.emplace_back(_vexList.size(), 0);
        nextMat.emplace_back(_vexList.size(), -1);
        for (int j = 0; j < _vexList.size(); j++) {
            if (i == j) {
                valueMat.at(i).at(j) = 0;
                nextMat.at(i).at(j) = j;
                continue;
            }
            auto res = outList.find(j);
            if (res == outList.end()) {
                valueMat.at(i).at(j) = EdgeNaN;
                nextMat.at(i).at(j) = -1;
            }
            else {
                valueMat.at(i).at(j) = res->second;
                nextMat.at(i).at(j) = j;
            }
        }
    }

    for (int i = 0; i < _vexList.size(); i++) {
        for (int j = 0; j < valueMat.size(); j++) {
            for (int k = 0; k < valueMat.size(); k++) {
                if (valueMat[j][i] == EdgeNaN || valueMat[i][k] == EdgeNaN)
                    continue;
                if (valueMat[j][i] + valueMat[i][k] < valueMat[j][k]) {
                    valueMat[j][k] = valueMat[j][i] + valueMat[i][k];
                    nextMat[j][k] = i;
                }
            }
        }
    }
}

void DiGraph::TopoOnAOV(std::vector<VexType>& topo) {
    topo.clear();
    std::vector<int> inDegree(_vexList.size(), 0);
    std::deque<int> zeroStack;
    for (auto i = _outEdgeList.begin(); i != _outEdgeList.end(); ++i) {
        for (auto j = i->second.begin(); j != i->second.end(); ++j) {
            inDegree.at(j->first)++;
        }
    }
    for (int i = 0; i < inDegree.size(); i++) {
        if (inDegree.at(i) == 0)
            zeroStack.push_back(i);
    }
    while (!zeroStack.empty()) {
        int top = zeroStack.front();
        zeroStack.pop_front();
        topo.emplace_back(_vexList.at(top));
        for (auto i = _outEdgeList.at(top).begin(); i != _outEdgeList.at(top).end(); ++i) {
            inDegree.at(i->first)--;
            if (inDegree.at(i->first) == 0)
                zeroStack.push_back(i->first);
        }
    }
}
